#
# @lc app=leetcode.cn id=47 lang=python
#
# [47] 全排列 II
#

# @lc code=start
### nums[i-1] != nums[i]法
# class Solution(object):
#     def permuteUnique(self, nums):
#         """
#         :type nums: List[int]
#         :rtype: List[List[int]]
#         """
#         self.nums = nums
#         self.nums.sort()
#         self.result = []
#         self.result_items = []
#         self.loop([False]*len(self.nums))
#         return self.result


#     def loop(self, used):
#         if len(self.result_items) == len(self.nums):
#             self.result.append(self.result_items[:])
#             return

#         for i in range(len(self.nums)):
#             if (i > 0 and self.nums[i] == self.nums[i-1] and used[i-1]) or used[i]:
#                 continue
#             self.result_items.append(self.nums[i])
#             used[i] = True
#             self.loop(used)
#             used[i] = False
#             self.result_items.pop()

class Solution(object):
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        self.nums = nums
        self.nums.sort()
        self.result = []
        self.result_items = []
        self.loop([False]*len(self.nums))
        return self.result

    def loop(self, used):
        if len(self.result_items) == len(self.nums):
            self.result.append(self.result_items[:])
            return
        
        cset = set()
        for i in range(len(self.nums)):
            if self.nums[i] in cset or used[i]:
                continue
            cset.add(self.nums[i])
            self.result_items.append(self.nums[i])
            used[i] = True
            self.loop(used)
            used[i] = False
            self.result_items.pop()
            
        
# @lc code=end

